package com.example.demo.algorithms;

import java.util.HashMap;

/**
 * <p>Description: 矩阵乘法链顺序demo</p>
 *
 * @author Eric Lee
 * @version v1.0.0
 * @since 2021/4/6 22:35
 **/
public class MatrixChainOrder {

    private int[][] arr;
    private static int[][] s;
    private int[] p;

    public MatrixChainOrder(int[] p, int[][] arr, int[][] s) {
        this.p = p;
        this.arr = arr;
        this.s = s;
    }

    public int[][] matrixChain() {
        int n = arr.length;
        //对角线上矩阵乘法的运算次数是0，因为是自己和自己，不用乘
        for (int i = 0; i < n; i++) {
            arr[i][i] = 0;
        }
        //三重循环
        //矩阵规模（从两个矩阵的乘法到n个矩阵的乘法）
        for (int r = 2; r <= n; r++) {
            //初始和结尾矩阵
            for (int i = 0; i <= arr.length - r; i++) {
                int j = i + r - 1;
                //假设决策为i时最优解，方便后面的比较
                arr[i][j] = arr[i + 1][j] + p[i] * p[i + 1] * p[j + 1];
                s[i][j] = i;
                //最优决策从i+1到j-1，如果k=2，规模为5，说明先做A0到A2的乘法，再做A3到A4的乘法是最优解，
                //AO到A2和A3到A4因为是规模比本次规模小的情况，其最优解已经记录在矩阵中了
                for (int k = i + 1; k < j; k++) {
                    int temp = arr[i][k] + arr[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
                    if (temp < arr[i][j]) {
                        arr[i][j] = temp;
                        s[i][j] = k;
                    }
                }
            }
        }
        return s;
    }

    //递归地输出问题解的格式
    public void show(int[][] s, int start, int end) {
        if (start != end) {
            System.out.print("(");
            show(s, start, s[start][end]);
            show(s, s[start][end] + 1, end);
            System.out.print(")");
        } else
            System.out.print("A" + (start + 1));
    }

    //主函数
    public static void main(String[] args) {
        //P指的是原始矩阵链的信息，例如A1-30*35,A2-35*15,A3—15*5,A4-5*10,A5-10*20,A6-20*25
        int[] p = new int[]{9, 6, 3, 21, 11, 5, 50};
        int[][] arr = new int[6][6];
        int[][] s = new int[6][6];
        MatrixChainOrder mc = new MatrixChainOrder(p, arr, s);
        s = mc.matrixChain();
        System.out.println("最少乘法计算次数是" + mc.arr[0][5]);
        System.out.println("按照如下格式计算可获得最优解");
        mc.show(s, 0, 5);
    }
}
